home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / cref.com / CREF.C next >
Encoding:
C/C++ Source or Header  |  1986-03-20  |  15.5 KB  |  565 lines
  1. /*********************************************************************/
  2. /*   Reference: The C Programming Tutor, Leon A. Wortman, Thomas     */
  3. /*        O. Sidebottom. pp 195-221                 */
  4. /*   Modified April 1, 1985 - A. DeSouza                 */
  5. /*********************************************************************/
  6. /*               include files                 */
  7. /*********************************************************************/
  8. #include <c:stdio.h>
  9. /*********************************************************************/
  10. /*                definitions                  */
  11. /*********************************************************************/
  12. #define BOOL          int
  13. #define DQUOTE          '"'
  14. #define EQUALS          0
  15. #define FALSE          0
  16. #define FIRSTGREATER  1
  17. #define FIRSTLESS     -1
  18. #define HTSIZE          1009   /* must be prime */
  19. #define MAXSTRLEN     255
  20. #define MAXWORDSIZE   20
  21. #define NULL          0
  22. #define SLASH          '/'
  23. #define SQUOTE          '\''
  24. #define STAR          '*'
  25. #define TRUE          1
  26. #define VOID          int
  27. #define MAXLNS          64    /* Maximum lines per page for Xerox */
  28. /*********************************************************************/
  29. /*                code macros                  */
  30. /*********************************************************************/
  31. #define PutBack(Ch)   {PutBackChar = Ch;  }
  32.  
  33. /*********************************************************************/
  34. /*                typedefs                     */
  35. /*********************************************************************/
  36. typedef struct rType {
  37.     int            Reference;        /* line number */
  38.     struct rType *Link;            /* link to next reference */
  39. }
  40. RefType, *RefPtr;
  41.  
  42. typedef struct tType {
  43.     char        *Value;         /* pointer to token */
  44.     RefPtr        OccurList;        /* line number list */
  45. }
  46. TokenType, *TokenPtr;
  47.  
  48. /*********************************************************************/
  49. /*                eternal functions                 */
  50. /*********************************************************************/
  51. extern char    *malloc();
  52. extern RefPtr    MakeOccurrence();
  53.  
  54. /*********************************************************************/
  55. /*                global variables                 */
  56. /*********************************************************************/
  57. int        CurLineNo = 1;            /* Line being read. */
  58. TokenType    HashTable [HTSIZE];
  59. int            PutBackChar = '\0';             /* Character put back after input */
  60. int            PageNo = 1;
  61. int            LnCount = 5;            /* Line count includes page break */
  62. char        FlagPg = FALSE;
  63. FILE        *FileOut;    /* Output file */
  64.  
  65. main (argc, argv)
  66.     int argc;
  67.     char *argv[];
  68.     {        /* main */
  69.     int        Counter;
  70.     char    CurToken [MAXSTRLEN];
  71.     char    c;
  72.     char    *ptrin, *ptrout;
  73.     FILE    *InFile;
  74.  
  75.     if (!(InFile = fopen(argv[1], "r"))) {
  76.         fprintf(stderr,"Can't open input file %s.\n", argv[1]);
  77.         exit(0);
  78.     }
  79.  
  80.     printf (" Output for Xerox 2700 Printer (Y/N): ");
  81.     c = toupper(getchar());
  82.     if (c == 'Y') FlagPg = TRUE;
  83.  
  84.     for (ptrout=CurToken, ptrin=argv[1]; *ptrin; ptrin++, ptrout++)
  85.         {
  86.         if (*ptrin == '.' || *ptrin == ' ')
  87.             break;
  88.         *ptrout = *ptrin;
  89.         }
  90.         *ptrout = '\0';
  91.         strcat (CurToken, ".lst");
  92.         FileOut = fopen(CurToken, "w");
  93.  
  94.     /* Initialize the hash table.
  95.      */
  96.     for (Counter = 0; Counter < HTSIZE; Counter++) {
  97.         HashTable[Counter].Value = NULL;
  98.         HashTable[Counter].OccurList = NULL;
  99.     }
  100.  
  101.     /* Write the first line numbr to the output stream.
  102.      */
  103.     fprintf(FileOut, " \t \t \t \t \t Page %d ", PageNo);
  104.     PageNo++;
  105.     fprintf(FileOut, "\n%4d    ", CurLineNo);
  106.  
  107.     /* Read and store each token.
  108.      */
  109.     while (GetNxtToken(CurToken, InFile)) {
  110.         if (InsertToken(CurToken)) {
  111.             fprintf(stderr, "Hash table size exceeded.\n");
  112.             break;
  113.         }
  114.     }
  115.     fprintf(FileOut, "   End-of-file.\n\n");
  116.  
  117.     /* sort the tokens alphabetically.
  118.      */
  119.     SortTokens(HTSIZE);
  120.  
  121.     PrintTable();
  122.     }    /* main */
  123.  
  124. VOID AddOccurrence(HeadPtr)
  125.     RefPtr    HeadPtr;
  126.     /* AddOccurrence adds a new line occurrence to the
  127.      * end of the list that HeadPtr begins.
  128.      */
  129.     {        /* AddOccurrence */
  130.     RefPtr    CurPtr;
  131.     RefPtr    NewPtr;
  132.  
  133.         /* Find the end of the list by starting at
  134.          * the beginning and advancing through the list
  135.          * until we find the end.  */
  136.         for (CurPtr = HeadPtr; CurPtr->Link != NULL;
  137.             CurPtr = CurPtr->Link)
  138.             ;
  139.  
  140.         CurPtr->Link = NewPtr = (RefPtr)malloc(sizeof(RefType));
  141.         if (NewPtr == NULL) {
  142.             fprintf("Out of Memory in AddOccurrence.");
  143.             exit(0);
  144.         }
  145.         NewPtr->Reference = CurLineNo;
  146.         NewPtr->Link = (RefPtr)NULL;
  147.         }    /* AddOccurrence */
  148.  
  149. char *Copy(OldString)
  150.     char    *OldString;
  151.     /* Copy makes a copy of OldString and returns the
  152.      * address of the copy.     */
  153.     {    /* Copy */
  154.     char    *NewString;
  155.  
  156.     /* Allocate a string able to hold the length of the
  157.      * string plus one for the terminator.    */
  158.     NewString = malloc(strlen(OldString) + 1);
  159.  
  160.     /* Copy the string and return a pointer to it.
  161.      */
  162.     strcpy(NewString, OldString);
  163.     return (NewString);
  164.     }    /* Copy */
  165.  
  166. int GenerateNewIndex(OriginalKey, ProbeNumber)
  167.     int    OriginalKey;
  168.     int ProbeNumber;
  169.  
  170.     /* GenerateNewIndex takes the current hash table index and
  171.      * generates a new index for collision resolution.
  172.      */
  173.     {    /* GenerateNewIndex */
  174.     return ((OriginalKey + ProbeNumber * ProbeNumber) % HTSIZE);
  175.     }    /* GenerateNewIndex */
  176.  
  177. int GetNxtChar(InputFile)
  178. FILE    *InputFile;
  179.     /* GetNxtChar returns the next non-comment
  180.      * a non-string character from Inputfile.
  181.      *
  182.      * At least one character is read from InputFile. If
  183.      * the character could start a comment the next character
  184.      * is checked. If the slash-star of a comment
  185.      * is read the reading of characters continues until the end
  186.      * of the comment is found.  If a single or double quote
  187.      * is read the reading of characters continues until
  188.      * the closing mark is found.  When end-of-file is encountered
  189.      * EOF is returned.  GetNxtChar therefore never returns
  190.      * characters inside comments or quotes.
  191.      */
  192.     {    /* GetNxtChar */
  193.     int    CheckChar;
  194.     int NewChar;
  195.     int TempChar;
  196.  
  197.     /* If end-of-file is found, return immediately.
  198.      */
  199.     if ((NewChar = GetRawChar(InputFile)) == EOF)
  200.         return(EOF);
  201.  
  202.     /* If a single or double quote is found, process the string.
  203.      */
  204.     if (NewChar == SQUOTE || NewChar == DQUOTE) {
  205.         CheckChar = NewChar;
  206.         /* Continue reading until the matching quote character
  207.          * is found.
  208.          */
  209.         while ((NewChar = GetRawChar(InputFile)) != CheckChar &&
  210.             NewChar != EOF);
  211.         /* The terminating character has now been read.
  212.          * Read one more and return it.
  213.          */
  214.         NewChar = GetRawChar(InputFile);
  215.     }
  216.     /* Next handle comment processing.  If SLASH is read,
  217.      * check to see if the next characte is a STAR.  If it is,
  218.      * continue reading until the matching STAR-SLASH is found.
  219.      */
  220.     else if (NewChar == SLASH) {
  221.         if ((TempChar = GetRawChar(InputFile)) != STAR) {
  222.             /* Not a comment; put back the character.
  223.              */
  224.             PutBack(TempChar);
  225.         }
  226.         else
  227.             /* Here's a comment.  Search for the end.
  228.              */
  229.             while (TRUE) {
  230.                 /* Read characters until a STAR is found.
  231.                  */
  232.                 while ((NewChar = GetRawChar(InputFile)) != STAR &&
  233.                     NewChar != EOF);
  234.  
  235.                 if ((NewChar = GetRawChar(InputFile)) == SLASH) {
  236.                     /* The end of the comment is found.
  237.                      */
  238.                     NewChar = GetRawChar(InputFile);
  239.                     break;
  240.                 }
  241.                 else
  242.                     /* Not end of comment.    Put the character back.
  243.                      */
  244.                     PutBack(NewChar);
  245.                 /* If end-of-file has been found, stop processing.
  246.                  */
  247.                 if (NewChar == EOF)
  248.                     break;
  249.             }
  250.         }
  251.         return (NewChar);
  252.     }    /* GetNxtChar */
  253.  
  254. BOOL GetNxtToken(Buffer, InputFile)
  255.     char    *Buffer;
  256.     FILE    *InputFile;
  257.     /* GetNxtToken returns in Buffer the next valid C token in the
  258.      * the program. */
  259.     {        /* GetNxtToken    */
  260.     int        CurChar;
  261.  
  262.     /* Read characters from Inputfile until starting letter is
  263.      * found.  Stop when find a valid letter or end-of-file.
  264.      */
  265.     while (!IsStartingLetter(CurChar = GetNxtChar(InputFile)) &&
  266.         CurChar != EOF)
  267.         ;
  268.  
  269.     /* Insert the first character.
  270.      */
  271.     *Buffer++ = CurChar;
  272.  
  273.     /* Read and accumulate characters in Buffer while they are
  274.      * valid letters for a token.
  275.      */
  276.     while (IsTokenLetter(CurChar = GetNxtChar(InputFile)) &&
  277.         CurChar != EOF)
  278.         *Buffer++ = CurChar;
  279.  
  280.     /* Put back the last character we read.
  281.      */
  282.     if (CurChar != EOF)
  283.         PutBack(CurChar);
  284.  
  285.     /* Terminate the token.
  286.      */
  287.     *Buffer = '\0';
  288.  
  289.     /* Return end-of-file status.
  290.      */
  291.     return ((CurChar == EOF) ? FALSE : TRUE);
  292.     }    /* GetNxtToken */
  293.  
  294. int    GetRawChar(InputFile)
  295.     FILE    *InputFile;
  296.     /* GetRawChar reads the next character from InputFile and
  297.      * returns it.    If a newline is read, it increments
  298.      * CurLineNo.  If end-of-file is read, it returns EOF.
  299.      */
  300.      {    /* GetRawChar */
  301.      int    NextChar;
  302.      /* Check PutBackChar to see if the next character has
  303.       * already been read.    If so, process it and set PutBackChar
  304.       * to the null character.
  305.       */
  306.      if (PutBackChar != '\0') {
  307.         NextChar = PutBackChar;
  308.         PutBackChar = '\0';
  309.         }
  310.      else {
  311.         /* Echo the character read to the output stream.
  312.          * If a newline is read, increment the line count.
  313.          */
  314.         if ((NextChar = getc(InputFile)) == '\n')  {
  315.             if (FlagPg)
  316.                 WrtEndPg();
  317.             fprintf(FileOut, "\n%4d    ", ++CurLineNo);
  318.         }
  319.         else
  320.             fputc(NextChar, FileOut);
  321.         }
  322.  
  323.     if (NextChar == EOF)
  324.         return(EOF);
  325.  
  326.     return(NextChar);
  327.     }    /* GetRawChar */
  328.  
  329. VOID WrtEndPg()
  330.     /* If end of page reached put blank line to make a page break
  331.      */
  332.     {    /* WrtEndPg */
  333.     LnCount++;
  334.     if ((LnCount % MAXLNS) == 0)  {
  335.         fprintf(FileOut, "  \n  \n  \n  \n");
  336.         fprintf(FileOut, " \t\t\t\t\t\t\t\t Page %d ", PageNo);
  337.         PageNo++;
  338.         LnCount += 4;
  339.     }
  340.     }    /* WrtEndPg */
  341.  
  342.  
  343. int Hash(Word)
  344.     char    *Word;
  345.     /* Hash returns the HTIndex of the Word passed, or an
  346.      * appropriate HTIndex for the word.  If HashTable is
  347.      * full, Hash returns -1 */
  348.     {    /* Hash */
  349.     int        HTIndex;
  350.     int        IdLen;
  351.     int        InitHTIndex;
  352.     int        ProbeCounter = 0;
  353.  
  354.     IdLen = strlen(Word);
  355.     if (IdLen == 0)
  356.         printf("Hash: Word of no length\n");
  357.     HTIndex = InitHTIndex = TransformId(Word);
  358.     if (HashTable[HTIndex].Value == NULL)
  359.         ;    /* NULL - We've got it. */
  360.     else    /* have we found the correct indes? */
  361.         if (strcmp(Word, HashTable[HTIndex].Value) == EQUALS)
  362.             ;    /* DONE: A direct hit! */
  363.         else    /* Collision - generate new indices */
  364.             for (ProbeCounter = 0; ProbeCounter < (HTSIZE / 2);
  365.                 ProbeCounter++) {
  366.                 HTIndex = GenerateNewIndex(InitHTIndex, ProbeCounter);
  367.                     if (HashTable[HTIndex].Value == NULL)
  368.                         break;        /* We've got it! */
  369.                     else if (strcmp(Word, HashTable[HTIndex].Value)
  370.                         == EQUALS)
  371.                         break;        /* We've got it! */
  372.                 }
  373.     if (ProbeCounter >= (HTSIZE / 2))
  374.         return(-1);
  375.     return(HTIndex);
  376.     }    /* Hash */
  377.  
  378. BOOL InsertToken(Token)
  379.     char    *Token;
  380.     /* InsertToken inserts the token into the hash table if it is
  381.      * new.  If the token is previously known, it adds the line
  382.      * number to the occurrence list.  It then returns FALSE.
  383.      * If the end-of-hash table is reached, TRUE is returned.
  384.      */
  385.     {        /* InsertToken */
  386.     int        HTIndex;
  387.  
  388.     HTIndex = Hash(Token);
  389.     if (HTIndex == -1)
  390.         return (TRUE);
  391.     if (HashTable[HTIndex].Value == NULL) {
  392.         HashTable[HTIndex].Value = Copy(Token);
  393.         HashTable[HTIndex].OccurList = MakeOccurrence();
  394.         }
  395.     else
  396.         AddOccurrence(HashTable[HTIndex].OccurList);
  397.  
  398.     return (FALSE);
  399.     }        /* InsertToken */
  400.  
  401. BOOL IsStartingLetter(Ch)
  402.     char    Ch;
  403.     /* IsStartingLetter returns TRUE if Ch is a valid character
  404.      * to begin a C token.
  405.      */
  406.     {    /*IsStartingLetter */
  407.     return ((isalpha(Ch) || Ch == '_') ? TRUE : FALSE);
  408.     }    /*IsStartingLetter */
  409.  
  410. BOOL IsTokenLetter(Ch)
  411.     char    Ch;
  412.     /* IsTokenLetter returns TRUE if Ch is a valid character
  413.      * inside a C token.
  414.      */
  415.     {    /* IsTokenLetter */
  416.     return ((isalpha(Ch) || isdigit(Ch) || Ch == '_') ? TRUE : FALSE);
  417.     }    /* IsTokenLetter */
  418.  
  419. RefPtr MakeOccurrence()
  420.     /* MakeOccurrence creates the first entry of the line occurrence
  421.      * list.  It creates the next node in the list, inserts CurLineNO
  422.      * and sets Link to NULL  in preparation for the next entry.
  423.      */
  424.     {    /* MakeOccurrence */
  425.     RefPtr        NewNode;
  426.  
  427.     if ((NewNode = (RefPtr)malloc(sizeof(RefType))) == NULL) {
  428.         fprintf("Out of memory in MakeOccurrence.");
  429.         exit(0);
  430.         }
  431.     NewNode->Reference = CurLineNo;
  432.     NewNode->Link = (RefPtr)NULL;
  433.  
  434.     return(NewNode);
  435.     }    /* MakeOccurrence */
  436.  
  437. int NameCompare(First, Second)
  438.     int        First;
  439.     int        Second;
  440.     /* NameCompare compares the two entries in HashTable referenced
  441.      * by the indices First and Second.  It returns FIRSTLESS if
  442.      * First < Second;  EQUALS if the equal;
  443.      * FIRSTGREATER if First > Second.
  444.      */
  445.     {    /* NameCompare */
  446.         /* If the first entry has no value, the first is less.
  447.          */
  448.         if (HashTable[First].Value == NULL)
  449.             return(FIRSTLESS);
  450.  
  451.         /* Then if the second has no value, the first is greater.
  452.          */
  453.         if (HashTable[Second].Value == NULL)
  454.             return(FIRSTGREATER);
  455.  
  456.         /* Otherwise return the comparison from strcmp.
  457.          */
  458.     return (strcmp(HashTable[First].Value, HashTable[Second].Value));
  459.     }    /* NameCompare */
  460.  
  461. VOID PrintTable()
  462.     /* PrintTable prints the list of identifiers and line occurrences.
  463.      */
  464.     {    /* PrintTable */
  465.     RefPtr        ListPtr;
  466.     int            NumOnLine;
  467.     int            TokenCounter;
  468.  
  469.     LnCount ++;
  470.     for (TokenCounter = 0; TokenCounter < HTSIZE;
  471.         TokenCounter++) {
  472.         if (HashTable[TokenCounter].Value) {
  473.             if (FlagPg)
  474.                 WrtEndPg();
  475.             fprintf(FileOut, "\n  %-20s   ", HashTable[TokenCounter].Value);
  476.             for (ListPtr = HashTable[TokenCounter].OccurList,
  477.             NumOnLine = 0; ListPtr != NULL;
  478.             ListPtr = ListPtr->Link, NumOnLine++) {
  479.                 if (NumOnLine == 10) {
  480.                     fprintf("FileOut, \n                         ");
  481.                     if (FlagPg)
  482.                         WrtEndPg();
  483.                     NumOnLine = 0;
  484.                     }
  485.                     fprintf(FileOut, "%3d  ", ListPtr->Reference);
  486.                 }
  487.             }
  488.         }
  489.         fprintf(FileOut, "\n");
  490.     }    /* PrintTable */
  491.  
  492. VOID SortTokens(SortNumber)
  493.     int        SortNumber;
  494.     /* SortTokens sorts the tokens into alphabetical order
  495.      * using a Shell sort.
  496.      */
  497.     {    /* SortTokens */
  498.     TokenType    Exchange;
  499.     int            BaseCounter;
  500.     int            CurCounter;
  501.     int            CurGapCounter;
  502.     int            Gap;
  503.     int            LastInBuf;
  504.  
  505.     LastInBuf = SortNumber;
  506.     /* Look through all Gaps starting with a gap half the
  507.      * size of the list.  Each time reduce the size of the
  508.      * gap by dividing by two.
  509.      */
  510.     for (Gap = LastInBuf / 2; Gap > 0; Gap /=2)
  511.  
  512.         /* BaseCounter moves between the Gap-th element and
  513.          * the last element in the list.  The sort using the
  514.          * current Gap runs until I is the LastInBuf-th
  515.          * element in the list.
  516.          */
  517.     for (BaseCounter = Gap; BaseCounter < LastInBuf; BaseCounter++)
  518.  
  519.         /* For an BaseCounter we compare the CurCounter-th and
  520.          * the CurGapCounter-th elements in the list.  CurCounter
  521.          * and CurGapCounter are always separated by Gap.
  522.          */
  523.     for (CurCounter = BaseCounter - Gap; CurCounter >= 0;
  524.         CurCounter -= Gap) {
  525.         CurGapCounter = CurCounter + Gap;
  526.  
  527.         /* If the two elements compare correctly, stop.
  528.          */
  529.             if (NameCompare (CurCounter, CurGapCounter) < EQUALS)
  530.                 break;
  531.  
  532.                 /* Otherwise, exchange the elements.
  533.                  */
  534.                 Exchange.Value =
  535.                     HashTable[CurCounter].Value;
  536.                 Exchange.OccurList =
  537.                     HashTable[CurCounter].OccurList;
  538.                 HashTable[CurCounter].Value =
  539.                     HashTable[CurGapCounter].Value;
  540.                 HashTable[CurCounter].OccurList =
  541.                     HashTable[CurGapCounter].OccurList;
  542.                 HashTable[CurGapCounter].Value =
  543.                     Exchange.Value;
  544.                 HashTable[CurGapCounter].OccurList =
  545.                     Exchange.OccurList;
  546.         }
  547.     }    /* SortTokens */
  548.  
  549. int TransformId(Word)
  550.     char    Word[];
  551.     /* TransformId converts the identifier into an integer
  552.      * within the index range of HashTable
  553.      */
  554.     {        /* transformId */
  555.     int        Term;
  556.     int        WordIndex;
  557.  
  558.     Term = 0;
  559.     for (WordIndex = strlen(Word) - 1; WordIndex > -1;
  560.         WordIndex--)
  561.         Term = (257 * Term) + Word[WordIndex];
  562.     Term = (Term < 0) ? -Term : Term;
  563.     return (Term % HTSIZE);
  564.     }        /* transformId */
  565.